{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. _nb_brkga:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Biased Random Key Genetic Algorithm (BRKGA)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A great and very informative presentation about BRKGAs can be found [here](http://mauricio.resende.info/talks/2012-09-CLAIO2012-brkga-tutorial-both-days.pdf). BRKGAs are known to perform well-known on combinatorial problems."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"display: block;margin-left: auto;margin-right: auto;width: 40%;\">\n",
    "![brkga](../resources/images/brkga.png)\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of customizing evolutionary operators a decoding has to be defined. Therefore, the evolution takes place simply on real-valued variables. \n",
    "\n",
    "Let us define a permutation problem which derives an order by sorting a real-valued variables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "code": "algorithms/usage_brkga.py",
    "section": "perm_prob"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from pymoo.model.problem import Problem\n",
    "\n",
    "\n",
    "class MyProblem(Problem):\n",
    "\n",
    "    def __init__(self, my_list):\n",
    "        self.correct = np.argsort(my_list)\n",
    "        super().__init__(n_var=len(my_list), n_obj=1, n_constr=0, xl=0, xu=1, elementwise_evaluation=True)\n",
    "\n",
    "    def _evaluate(self, x, out, *args, **kwargs):\n",
    "        pheno = np.argsort(x)\n",
    "        out[\"F\"] = - float((self.correct == pheno).sum())\n",
    "        out[\"pheno\"] = pheno\n",
    "        out[\"hash\"] = hash(str(pheno))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since duplicate eliminates is a very import aspect for evolutionary algorithm, we have to make sure all duplicates with respect to the permutation (and not to the real values) are filtered out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "code": "algorithms/usage_brkga.py",
    "section": "dupl"
   },
   "outputs": [],
   "source": [
    "from pymoo.model.duplicate import ElementwiseDuplicateElimination\n",
    "\n",
    "\n",
    "class MyElementwiseDuplicateElimination(ElementwiseDuplicateElimination):\n",
    "\n",
    "    def is_equal(self, a, b):\n",
    "        return a.get(\"hash\")[0] == b.get(\"hash\")[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we define a problem which has to sort a list by their values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "code": "algorithms/usage_brkga.py",
    "section": "problem"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted by [ 1 19 12 14  6  9  8  5  4  3  0 17 13 11  2  7 10 15 18 16]\n"
     ]
    }
   ],
   "source": [
    "np.random.seed(2)\n",
    "list_to_sort = np.random.random(20)\n",
    "problem = MyProblem(list_to_sort)\n",
    "print(\"Sorted by\", np.argsort(list_to_sort))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we use BRKGA to obtained the sorted list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "code": "algorithms/usage_brkga.py",
    "section": "solve"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Best solution found: \n",
      "X = [0.62512107 0.00210869 0.73537788 0.60261201 0.43045971 0.38763854\n",
      " 0.19209895 0.80429496 0.35157945 0.25393386 0.80567794 0.73484463\n",
      " 0.10660141 0.66239025 0.1506689  0.92465587 0.98896201 0.63240497\n",
      " 0.94057641 0.07739991]\n",
      "F = [-20.]\n",
      "Solution [ 1 19 12 14  6  9  8  5  4  3  0 17 13 11  2  7 10 15 18 16]\n",
      "Optimum  [ 1 19 12 14  6  9  8  5  4  3  0 17 13 11  2  7 10 15 18 16]\n"
     ]
    }
   ],
   "source": [
    "from pymoo.algorithms.so_brkga import BRKGA\n",
    "from pymoo.optimize import minimize\n",
    "\n",
    "algorithm = BRKGA(\n",
    "    n_elites=200,\n",
    "    n_offsprings=700,\n",
    "    n_mutants=100,\n",
    "    bias=0.7,\n",
    "    eliminate_duplicates=MyElementwiseDuplicateElimination())\n",
    "\n",
    "res = minimize(problem,\n",
    "               algorithm,\n",
    "               (\"n_gen\", 75),\n",
    "               seed=1,\n",
    "               verbose=False)\n",
    "\n",
    "print(\"Best solution found: \\nX = %s\\nF = %s\" % (res.X, res.F))\n",
    "print(\"Solution\", res.opt.get(\"pheno\")[0])\n",
    "print(\"Optimum \", np.argsort(list_to_sort))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### API"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. autoclass:: pymoo.algorithms.so_brkga.BRKGA\n",
    "    :noindex:"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
